package org.senf.outerspace.engine.pathing;

import java.util.ArrayList;
import java.util.List;

import org.eclipse.swt.graphics.Point;

public class GalaxyPather {

	private List<Node> open;
	private List<Node> closed;

	private boolean found;
	private boolean stopped;
	
	private Point min;
	private Point max;
	
	public GalaxyPather(Point min, Point max) {
		open = new ArrayList<Node>();
		closed = new ArrayList<Node>();
		found = false;
		stopped = false;
		this.min = min;
		this.max = max;
	}
	
	public static void main(String[] args) {
		Point p1 = new Point(1,1);
		Point p2 = new Point(7,2);
		
		Point min = new Point(0,0);
		Point max = new Point(10,10);
		Point[] route = new GalaxyPather(min,max).getRoute(p1, p2);
		
		System.out.println("Shortest route: " + (route.length-1) + " steps:");
		for (Point p: route) {
			System.out.print(p.x + "," + p.y + " -> ");
		}
		System.out.println("Done");
	}
	
	public Point[] getRoute(Point p1, Point p2) {
		
		Node a = Node.create(p1);
		Node b = Node.create(p2);
		
		int cost = Heuristic.getDistance(a, b);
		a.h = cost;
		
		Utils.addUnique(open, a);
		
		while (!found && !stopped) {
			walk(b);
		}
		
		if (found) {
			Node node = closed.get(closed.size()-1);
			List<Node> path = new ArrayList<Node>();
			path.add(node);
			while (node.parent != null) {
				path.add(node.parent);
				node = node.parent;
			}
			Point[] pts = new Point[path.size()];
			for (int i=0;i<pts.length;i++) {
				node = path.get(pts.length-(i+1));
				pts[i] = new Point(node.x,node.y);
			}
			return pts;
		} else {
			return null;
		}
	}
	
	private void walk(Node target) {
		Node current = getCheapestNode(target);
		open.remove(current);
		Utils.addUnique(closed, current);
		
		if (current.x == target.x && current.y == target.y) {
			found = true;
			stopped = true;
		}
		
		boolean validNodes = false;
		for (int dir = 1; dir <= 8; dir++) {
			Node child = current.child(dir);
			
			if (child.x < min.x || child.x > max.x || child.y < min.y || child.y > max.y) {
				// Child is not part of the grid.
				continue;
			}
			
			int cost = Heuristic.getDistance(child, target);
			child.h = cost;
			
			validNodes = true;
			if (!closed.contains(child)) {
				if (open.contains(child)) {
					int i = open.indexOf(child);
					Node existing = open.get(i);
					if (child.g < existing.g) {
						open.remove(existing);
						open.add(child);
					}
				} else {
					open.add(child);
				}
			}
		}
		if (!validNodes) {
			stopped = true;
		}
	}
	
	private Node getCheapestNode(Node target) {
		Node cheapest = null;
		for (Node n: open) {
			if (cheapest == null || n.getCost() < cheapest.getCost()) {
				cheapest = n;
			}
		}
		return cheapest;
	}
}
